#ifndef _LOTTERY_H_
#define _LOTTERY_H_

#include <set>
#include <vector>
#include "BaselineRandomWalk.h"

using namespace std;

class IndexTree//SUMTREE use bit
{
public:
    //TODO: make it resizable...
    void resize(int Size){for(Size++,size=1;size<Size;size<<=1);Store.resize(size);};
	void Add(int Index, double Value){for(Index++;Index<=size;Index+=RightBit(Index))Store[Index-1]+=Value;};
    void setZero() {fill(Store.begin(), Store.end(), 0.0);}
	double Ask(int From,int To);
private:
	int RightBit(int x){return x&(x^(x-1));};
	int size;
	vector<double> Store;
};

class LotteryRandomWalk : public BaseCrawler
{
public:
    LotteryRandomWalk(API *network) : BaseCrawler(network) {
        //TODO: make degreeCount resizable
        degreeCount.resize(1000000);
        unexploredCount = 0;
    }
protected:
    virtual void updateDiscoveredNode(int discoveredNode);
    virtual int nodeToExplore();

    int unexploredCount;
    IndexTree degreeCount;
    vector<int> nodeIDs; //list of nodeIDs ordered by index in degreeCount
    map<int,int> visitedNode;// <nodeID, index in vector nodeIDs>
};

#endif
